package com.kavinz.algo.tree;

import com.kavinz.algo.list.DoublyLinkedList;

/**
 * Recursive implementation of BST(abbr. of Binary Search Tree)
 * 
 * @author Kevin Zhao
 * 
 */
public class RecursiveBST<ValueType> implements IBST<ValueType> {

	private Node root;

	class Node {
		Comparable key;
		ValueType value;
		Node leftChild;
		Node rightChild;
		Node parent;
	}

	public void put(Comparable key, ValueType value) {
		// insert the new node, seting it as the new root node
		insert(root, key, value);
	}

	private Node insert(Node oldRoot, Comparable key, ValueType value) {
		// construct new node
		Node newNode = new Node();
		newNode.key = key;
		newNode.value = value;
		// if the tree is empty
		if (oldRoot == null) {
			// update the root node reference
			root = newNode;
		}
		// non-empty tree
		else {
			if (key.compareTo(oldRoot.key) > 0) {
				Node rightChild = oldRoot.rightChild;
				if (rightChild == null) {
					// right subtree does not exist
					oldRoot.rightChild = newNode;
					newNode.parent = oldRoot;
				} else {
					// insert in right subtree
					insert(rightChild, key, value);
				}
			} else if (key.compareTo(oldRoot.key) == 0) {
				// update the oldRoot's value field with new value
				oldRoot.value = newNode.value;
			} else {
				Node leftChild = oldRoot.leftChild;
				if (leftChild == null) {
					// left subtree does not exist
					oldRoot.leftChild = newNode;
					newNode.parent = oldRoot;
				} else {
					// insert in left subtree
					insert(leftChild, key, value);
				}
			}
		}

		return newNode;

	}

	public ValueType get(Comparable key) {
		if (root == null)
			return null;
		Node node = search(root, key);
		if (node != null)
			return node.value;
		else
			return null;
	}

	private Node search(Node oldRoot, Comparable key) {
		Node result = null;
		if (key.compareTo(oldRoot.key) > 0) {
			Node rightChild = oldRoot.rightChild;
			if (rightChild == null) {
				// right subtree does not exist
				return null;
			} else {
				// continue searching in right subtree
				result = search(rightChild, key);
			}
		} else if (key.compareTo(oldRoot.key) == 0) {
			// search hit
			return oldRoot;
		} else {
			Node leftChild = oldRoot.leftChild;
			if (leftChild == null) {
				// left subtree does not exist
				return null;
			} else {
				// continue search in left subtree
				result = search(leftChild, key);
			}
		}
		return result;
	}

	/**
	 * <Cracking the coding interview><br>
	 * Exercise 4.1<br>
	 * Implement a function to check if a tree is balanced. For the purposes of
	 * this question, a balanced tree is defined to be a tree such that no two
	 * leaf nodes differ in distance from the root by more than one
	 */
	public boolean isBalance() {
		int minDepth = 0;
		int maxDepth = 0;
		int curDepth = 0;
		int[] result = calDepth(curDepth, minDepth, maxDepth, root);

		return result[2] - result[1] < 2;
	}

	private int[] calDepth(int curDepth, int minDepth, int maxDepth,
			Node rootNode) {
		int[] result = new int[] { curDepth, minDepth, maxDepth };

		if (rootNode == null)
			return result;

		// rootNode non-null
		curDepth++;

		if (rootNode.leftChild != null) {
			result = calDepth(curDepth, result[1], result[2],
					rootNode.leftChild);
		}
		if (rootNode.rightChild != null) {
			result = calDepth(curDepth, result[1], result[2],
					rootNode.rightChild);
		}

		// rootNode is a leafNode
		if (rootNode.leftChild == null && rootNode.rightChild == null) {
			if (result[1] == 0)
				result[1] = result[0];
			result[1] = result[0] < result[1] ? curDepth : result[1];
			result[2] = result[0] > result[2] ? curDepth : result[2];
		}

		return result;
	}

	/**
	 * <Cracking the coding interview><br>
	 * Exercise 4.4<br>
	 * Given a binary search tree, design an algorithm which creates a linked
	 * list of all the nodes at each depth (i e , if you have a tree with depth
	 * D, you’ll have D linked lists)
	 */
	public DoublyLinkedList[] depthArray = new DoublyLinkedList[100];

	public void constructDepthArray(Node node, int depth) {
		if (node == null)
			return;

		DoublyLinkedList depthObj = depthArray[depth];
		if (depthObj == null)
			depthObj = depthArray[depth] = new DoublyLinkedList();
		depthObj.add(node);

		constructDepthArray(node.leftChild, depth + 1);
		constructDepthArray(node.rightChild, depth + 1);

	}

	/**
	 * <Cracking the coding interview><br>
	 * Exercise 4.5<br>
	 * Write an algorithm to find the ‘next’ node (e g , in-order successor) of
	 * a given node in a binary search tree where each node has a link to its
	 * parent <br>
	 * Note:Traverse left node, current node, then right [usually used for
	 * binary search trees]
	 * 
	 * @param key
	 * @param isRightChildVisited
	 * @return
	 */
	public ValueType successor(Comparable key, boolean isRightChildVisited) {
		Node successor = null;
		Node node = search(root, key);
		if (node == null)
			return null;

		// if the specified node has right child,then the successor of it must
		// be the right child itself or ,if right child has subtree,located in
		// the left-most child of right
		// child's subtree
		if (node.rightChild != null && isRightChildVisited == false) {
			successor = leftMostChild(node.rightChild);
			return successor.value;
		} else {
			Node parent = node.parent;
			if (parent == null)
				return null;
			if (node == parent.leftChild)
				return parent.value;
			if (node == parent.rightChild)
				return successor(parent.key, true);
		}
		return null;
	}

	private Node leftMostChild(Node root) {
		if (root == null)
			return null;

		Node leftMostChild = leftMostChild(root.leftChild);
		if (leftMostChild == null)
			return root;
		else
			return leftMostChild;

	}

	/**
	 * if the specified node has only one child,then replace that node with its
	 * child if it's a node having two children,we replace that node with the
	 * left-most node of that node's right subtree. <br>
	 * Reference:<link>http://www.algolist.net/Data_structures/
	 * Binary_search_tree/Removal</link>
	 * 
	 * @param key
	 */
	public void remove(Comparable key) {
		Node nodeToDel = search(root, key);

		if (nodeToDel == null)
			return;
		// 1.no children
		if (nodeToDel.leftChild == null && nodeToDel.rightChild == null) {
			if (nodeToDel.parent.leftChild == nodeToDel)
				nodeToDel.parent.leftChild = null;
			else if(nodeToDel.parent == null)
				root = null;
			else
				nodeToDel.parent.rightChild = null;
		}
		// 2.one child
		if (nodeToDel.leftChild != null && nodeToDel.rightChild == null
				|| nodeToDel.rightChild != null && nodeToDel.leftChild == null) {
			if (nodeToDel.parent.leftChild == nodeToDel)
				nodeToDel.parent.leftChild = nodeToDel.leftChild == null ? nodeToDel.rightChild
						: nodeToDel.leftChild;
			else if(nodeToDel.parent == null)
				root = nodeToDel.leftChild == null ? nodeToDel.rightChild
						: nodeToDel.leftChild;
			else
				nodeToDel.parent.rightChild = nodeToDel.leftChild == null ? nodeToDel.rightChild
						: nodeToDel.leftChild;
		}

		// 3.two children
		if (nodeToDel.leftChild != null && nodeToDel.rightChild != null) {
			Node leftMostChildNode = leftMostChild(nodeToDel.rightChild);
			// replacement
			nodeToDel.key = leftMostChildNode.key;
			nodeToDel.value = leftMostChildNode.value;
			// eliminating the duplication
			leftMostChildNode.parent.leftChild = null;
		}

	}

	/**
	 * <Cracking the coding interview><br>
	 * Exercise 4.7<br>
	 * You have two very large binary trees: T1, with millions of nodes, and T2,
	 * with hun- dreds of nodes Create an algorithm to decide if T2 is a subtree
	 * of T1
	 * 
	 * @param t1
	 *            smaller tree
	 * @param t2
	 *            bigger tree
	 * @return
	 */
	public boolean contains(RecursiveBST t1, RecursiveBST t2) {
		Node t2SMatchingRoot = (Node) t2.search(t2.root, t1.root.key);
		if (t2SMatchingRoot == null)
			return false;
		if(t1 == null)//empty tree is always a subTree
			return true;

		return subTree((Node) t1.root, t2SMatchingRoot);
	}

	public boolean subTree(Node n1, Node n2) {
		// we're running out the smaller tree
		if (n1 == null)
			return true;
		// bigger tree is empty 
		if (n2 == null)
			return false;

		return n1.value == n2.value && subTree(n1.leftChild, n2.leftChild)
				&& subTree(n1.rightChild, n2.rightChild);

	}
	
	
	public static void main(String[] args) {
		RecursiveBST<String> tree = new RecursiveBST<String>();
		RecursiveBST<String> tree1 = new RecursiveBST<String>();
		tree.put("S", "S");
		tree.put("E", "E");
		tree.put("A", "A");
		tree.put("R", "R");
		tree.put("C", "C");
		tree.put("H", "H");

		tree.put("V", "V");
		tree.put("U", "U");
		tree.put("W", "W");
		tree.put("X", "X");
		tree.put("Y", "Y");
		tree.put("Z", "Z");

		
		tree1.put("E", "E");
		tree1.put("A", "A");
		tree1.put("R", "R");
		tree1.put("C", "C");
		tree1.put("H", "H");
//		tree1.put("D", "D");
		tree1.remove("E");
		
		System.out.println(tree.contains(tree1, tree));
		
		System.out.println(tree.get("R"));
		// System.out.println(tree.isBalance());
		tree.constructDepthArray(tree.root, 0);
		System.out.println(tree.depthArray.length);

		System.out.println(tree.successor("B", false));// should be null
		System.out.println(tree.successor("E", false));// should be H
		tree.remove("C");
		System.out.println(tree.successor("A", false));// should be E
		System.out.println(tree.successor("R", false));// should be S
	}
}
